#include "GeometryUtils.h"
#include "Model3D.h"
#include <memory>

class Triangle3D;

class KDTree
	{

	private:
		
		struct Node; 
		
		static std::pair<TBox3, TBox3> _DivideBoundingBox(const TBox3& box);
		std::shared_ptr<Node> mp_root; 
		
		size_t m_number_of_triangles; // additional information for debugging
		size_t m_max_recursion_depth; // additional information for debugging

		static void _CreateTree(std::vector<const Triangle3D*>& io_triangles, std::shared_ptr<KDTree::Node> io_node);
		void KDTree::_PickTriangle(std::set<const Triangle3D*>& io_triangles, const TLine3& io_line, const std::shared_ptr<KDTree::Node> i_node);
		static void _FitTBoxForTriangles(TBox3& io_bounding_box, const std::vector<const Triangle3D*>& i_triangles);
		static std::pair<double, double> _FindMaxMinCoordinate (const Triangle3D* i_triangle, const size_t i_dimention);
		
		static size_t _HowManyTriangles(std::shared_ptr<KDTree::Node> i_node); // additional method for debugging
	public:
		HSMODEL_API KDTree(Model3D::Triangle3DIteratorConst i_begin, Model3D::Triangle3DIteratorConst i_end);
		HSMODEL_API std::vector<const Triangle3D*> PickTriangles(const TLine3& i_line);
		
	};

struct KDTree::Node
	{
	public:
		std::shared_ptr<Node> mp_left; 
		std::shared_ptr<Node> mp_right;
		std::shared_ptr<Node> mp_middle;
		TBox3 m_bounding_box;
		std::vector <const Triangle3D*> m_triangles; //not empty only in leaf

		size_t m_triangles_in_subtree;

	public:
		Node();
		Node(TBox3&);
	};